package demo.practice.trie;

public class P1707 {


    public int[] maximizeXor(int[] nums, int[][] queries) {
        int[] target = new int[queries.length];

        for (int i = 0; i < queries.length; i++) {
            int max = -1;
            int maxi = queries[i][1];

            XorTrie trie = new XorTrie();
            for (int j = 0; j < nums.length; j++) {
                if (nums[j] <= maxi) {
                    trie.insert(nums[j]);
                }
            }
            target[i] =   trie.size==0?-1 :trie.XorMax(queries[i][0]);
        }
        return target;
    }

}


/*
class P1707Trie {
    Map<Integer, P1707Trie> child = new HashMap<>();

    public void insert(int num) {
        P1707Trie cur = this;
        for (int i = 30; i >= 0; i--) {
            int bit = (num >> i) & 1;
            if (cur.child.get(bit) == null) {
                cur.child.put(bit, new P1707Trie());
                cur = cur.child.get(bit);
            } else {
                cur = cur.child.get(bit);
            }
        }
    }

    public void insert(int[] nums) {
        for (int num : nums) {
            insert(num);
        }
    }


    public int XorMax(int num, int maxi) {
        P1707Trie cur = this;
        int res = 0;


        boolean bigger = false;
        for (int i = 30; i >= 0; i--) {
            int bit = (num >> i) & 1;
            int xorbit = (maxi >> i) & 1;   //当前位的当前bit位，会左右当前这个位置的选择
            if(!bigger&&xorbit==0){
                //这时候，异或bit位只能0,因为要比maxi小
                if(cur.child.get(0)==n)
            }

            //if(xorbit)
            */
/*if (bit == 0) {
                if (cur.child.get(1) != null) {
                    //这一位有值
                    res = res | (1 << i);
                    cur = cur.child.get(1);

                } else {
                    cur = cur.child.get(0);
                }
            } else {
                if (cur.child.get(0) != null) {
                    //这一位有值
                    res = res | (1 << i);
                    cur = cur.child.get(0);
                } else {

                    cur = cur.child.get(1);
                }
            }*//*

        }
        return res;
    }


}*/
